/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
import java.util.Vector;
/**
 *
 * @param <E> Parametro que permite objetos de cualquier clase haciendo generica, pero solo si el objeto extiende de la clase comparable.
 * @author Alejo
 */
public class VectorHeap<E extends Comparable<E>>  implements PriorityQueue <E> {
   
    
    /**
     * Atributo vector en el cual se ordenara como arbol binario, por prioridad
     */
    protected Vector<E> data; // the data, kept in heap order

    /**
     * Constructor de una nueva cola de prioridad, genera un nuevo vector vacio.
     */
    public VectorHeap(){
        data = new Vector<E>();
    }
    /**
     * Constructor con un vector como parametro, de una nueva cola de prioridad
     * @param v Es un vector el cual se del cual se utilizara como base para la nueva cola de prioridad
     */
    public VectorHeap(Vector<E> v){
        int i;
        data = new Vector<E>(v.size());
        for (i = 0; i < v.size(); i++)
            { 
                add(v.get(i));
            }
    }
    /**
     * Procedimiento que devuelve el indice del padre a partir del indice del hijo.
     * @param i valor del indice del hijo en la cola.
     * @return el valor del indice del padre en la cola.
     */
    protected static int parent(int i){
        return (i-1)/2;
    }
    /**
     * Procedimiento que devuelve el valor del indice del hijo izquierdo, a partir del indice del padre
     * @param i Es el valor del indice del padre
     * @return El valor del indice del hijo.
     */
    protected static int left(int i){
    return 2*i+1;
    }
    /**
     * Procedimiento que devuelve el valor del indice del hijo derecho, a partir del indice del padre.
     * @param i Es el valor del indice del padre
     * @return Es el valor del indice del hijo derecho
     */
    protected static int right(int i){
    return 2*(i+1);
    }

    /**
     * Procedimiento que mueve el nodo hijo a su posicion apropiada por prioridad.
     * @param leaf es el indice del hijo a ordenar, o mas bien del extremo al cual se va ordenar.
     */
    protected void percolateUp(int leaf){
    int parent = parent(leaf);
    E value = data.get(leaf);
    while (leaf > 0 && (value.compareTo(data.get(parent)) < 0))
        {
         data.set(leaf,data.get(parent));
         leaf = parent;
         parent = parent(leaf);
        }
    data.set(leaf,value);
    }
    
    /**
     * Procedimiento que permite si se retira la raiz, generar un nuevo arbol ordenado 
     * subiendo un hijo y bajando la raiz.
     * @param root Es el indice de la raiz.
     */
    protected void pushDownRoot(int root){
    int heapSize = data.size();
    E value = data.get(root);
    while (root < heapSize) 
        {
         int childpos = left(root);
         if (childpos < heapSize)
            {
                if ((right(root) < heapSize) && ((data.get(childpos+1)).compareTo (data.get(childpos)) < 0))
                    {
                    childpos++;
                    }
   
                 if ((data.get(childpos)).compareTo(value) < 0)
                    {
                    data.set(root,data.get(childpos));
                    root = childpos; 
                    } else 
                    { 
                     data.set(root,value);
                    return;
                    }
               } 
         else 
            { 
            data.set(root,value);
            return;
            }
        }
    }
    
    @Override
    public E getFirst() {
        return data.get(0);
    }

    @Override
    public E remove() {
        E minVal = getFirst();
        data.set(0,data.get(data.size()-1));
        data.setSize(data.size()-1);
        if (data.size() > 1) pushDownRoot(0);
        return minVal;
    }

    @Override
    public void add(E value){
    data.add(value);
    percolateUp(data.size()-1);
    }

    @Override
    public boolean isEmpty() {
        boolean vac = true;
       if ( size() == 0)
           vac = true;
       else 
            vac = false;
       return vac;
           
    }

    @Override
    public int size() {
        int tamano = data.size();
        return tamano;
    }

    @Override
    public void clear() {
        throw new UnsupportedOperationException("Not supported yet.");
    }
    
    public String toString(){
        String s = data.toString();
        return s;
    }
    
}
